package ljl.codetop300;

import java.util.Arrays;

/**
 * 3 sum 我都不会还来个 closest？
 *
 * 谷歌 facebook 都考，宁配去吗？
 *
 * 不太明白，我居然做对了？
 */
public class _16_3_sum_closest {

  /**
   * 感觉上就是：按住第一个，然后剩下的双指针，可以不
   */
  static class test {
    public static void main(String[] args) {
      int res = new test().threeSumClosest(new int[]{-1,2,1,-4}, 1);
      System.out.println(res);
    }
    public int threeSumClosest(int[] nums, int target) {
      Arrays.sort(nums);
      int diff = Integer.MAX_VALUE;
      int res = diff;
      for (int i = 0; i < nums.length; i++) {
        int remainder = target - nums[i];
        int l = i + 1;
        int r = nums.length - 1;
        while (l < r) {
          int sum = nums[l] + nums[r];
          int currentDiff = Math.abs(sum - remainder);
          if (currentDiff < diff) {
            res = sum + nums[i];
            diff = currentDiff;
          }
          if (sum < remainder) {
            l++;
          } else {
            r--;
          }
        }
      }
      return res;
    }
  }

  /**
   * 他的解法比我的确实要更优一点
   *
   * 有没有搞错，性能比我的差三分之一？
   */
  static class off {
    public int threeSumClosest(int[] nums, int target) {
      Arrays.sort(nums);
      int n = nums.length;
      int best = 10000000;

      // 枚举 a
      for (int i = 0; i < n; ++i) {
        // 保证和上一次枚举的元素不相等
        if (i > 0 && nums[i] == nums[i - 1]) {
          continue;
        }
        // 使用双指针枚举 b 和 c
        int j = i + 1, k = n - 1;
        while (j < k) {
          int sum = nums[i] + nums[j] + nums[k];
          // 如果和为 target 直接返回答案
          if (sum == target) {
            return target;
          }
          // 根据差值的绝对值来更新答案
          if (Math.abs(sum - target) < Math.abs(best - target)) {
            best = sum;
          }
          if (sum > target) {
            // 如果和大于 target，移动 c 对应的指针
            int k0 = k - 1;
            // 移动到下一个不相等的元素
            while (j < k0 && nums[k0] == nums[k]) {
              --k0;
            }
            k = k0;
          } else {
            // 如果和小于 target，移动 b 对应的指针
            int j0 = j + 1;
            // 移动到下一个不相等的元素
            while (j0 < k && nums[j0] == nums[j]) {
              ++j0;
            }
            j = j0;
          }
        }
      }
      return best;
    }
  }

  /**
   * 我这个比官方题解快一点，但是比我那个居然还慢一些？
   */
  static class copy_off {
    public int threeSumClosest(int[] nums, int target) {
      Arrays.sort(nums);
      int res = Integer.MAX_VALUE;
      int diff = Integer.MAX_VALUE;
      for (int i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int rest = target - nums[i];
        int l = i + 1;
        int r = nums.length - 1;
        while (l < r) {
          int twoSum = nums[l] + nums[r];
          if (twoSum == rest) return target;
          int curDiff = Math.abs(rest - twoSum);
          if (curDiff < diff) {
            diff = curDiff;
            res = twoSum + nums[i];
          }
          if (twoSum < rest) {
            while (l < r && nums[l + 1] == nums[l]) l++;
            l++;
          } else {
            while (l < r && nums[r - 1] == nums[r]) r--;
            r--;
          }
        }
      }
      return res;
    }
  }

  /**
   * 这是我最早一次提交的，这个居然最快，只有 7ms
   * 但是我提交了一次，这个不如上面那个快，到 13ms 了，说明力扣服务器是不稳定的
   */
  static class whos {
    public int threeSumClosest(int[] nums, int target) {
      Arrays.sort(nums);
      int res = Integer.MAX_VALUE;

      for (int i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1])
          continue;
        int l = i + 1, r = nums.length - 1;
        while (l < r) {
          int sum = nums[i] + nums[l] + nums[r];
          if (sum == target) {
            return target;
          }
          if (res == Integer.MAX_VALUE || Math.abs(sum - target) < Math.abs(res - target))
            res = sum;
          if (sum > target) {
            r--;
          } else {
            l++;
          }
        }
      }
      return res;
    }
  }

  static class copy_old {
    public int threeSumClosest(int[] nums, int target) {
      Arrays.sort(nums);
      int res = Integer.MAX_VALUE;
      for (int i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int l = i + 1;
        int r = nums.length - 1;
        while (l < r) {
          int sum = nums[i] + nums[l] + nums[r];
          if (sum == target) return target;
          if (Math.abs(target - sum) < Math.abs(target - res)) res = sum;
          if (sum > target) r--;
          else l++;
        }
      }
      return res;
    }
  }
}
